스택

이전 시간에 일반 배열과 동적 배열로 '스택'이라는 ADT를 구현했다.

링크드 리스트로 스택 구현

push : 맨 앞에 항목을 삽입하는 것으로 구현한다.

1. 새 노드를 만들고
2. head의 포인터에 있는 주소값을 가져오고
3. 새 노드의 포인터에 가져온 주소값을 넣고
4. 자신의 주소값을 head에게 가리키게 한다.

pop : 첫 노드(header/top node)를 삭제하는것으로 구현한다.

1. 임시 노드를 만들고
2. head가 가리키는 주소값을 임시 노드의 포인터에 할당.
3. 탑 노드의 값과 탑 노드의 포인터에 있는 주소값을 가져온다.
4. 헤드포인터를 탑노드에서 가져온 포인터로 바꾸고
5. 임시 노드가 가지고있는 탑 노드의 주소값을 free()해주고
6. 3번의 탑 노드 안에 있는 값을 반환.

전체 삭제

이 방법은 사실 링크드리스트를 삭제하는 방법과 동일하다.
(저번시간에 노트를 안해서 여기다가 함)

1. 임시 포인터를 만들어 탑노드의 주소값을 가져와 가리키게 한다.
2. 헤드포인터를 그 다음 노드를 가리키게 하고
3. 임시 포인터를 사용해 free()해서 1번에서 가져온 탑노드를 지운다
4. 이 과정을 헤드포인터가 null일때 까지.

void clearStack(Node **head_ptr) {
    Node *head = *head_ptr; 
    Node *temp = NULL;
    
    while (head != NULL) {
        temp = head; 
        head = head->next; 
        free(temp);
    }
    
    *head_ptr = NULL; 
}

큐

스택이랑은 반대로 먼저 들어간것이 먼저 나오는 자료구조.
FIFO - Fist In First Out.

push와 pop 대신 EnQueue와 DeQueue를 사용.
push가 맨 앞에 넣기라면, EnQueue는 맨 뒤에 넣기.
pop과 DeQueue는 모두 맨 앞에서 제거하기.

어레이로 구현

원형

스택에서는 들어가는 쪽과 꺼내는 쪽의 방향이 똑같다.
하지만 큐는 들어가는건 뒤에서 들어가고, 꺼낼때는 앞에서 꺼낸다. 방향이 다르다.
그래서 일반 어레이로 큐를 구현하면, 배열의 앞 공간이 낭비될 수 있다. 길이 5의 어레이 [1,2,3,4,5]에서 1과 2가 빠지면 [ , ,3,4,5]가 된다.
인큐는 뒤에서부터 넣기때문에, 뒤에 공간이 없기 때문에 더이상 넣을 수 없게 된다(앞에 두 자리가 비어있음에도 불구하고).

그래서 (개념적으로)선형이 아닌 원형인 어레이를 사용한다.

이걸 구현하는 방법은 front, rear 포인터를 사용하는 것이다.

처음에 어레이를 만들때 front,rear 모두 -1으로 할당한다. (비어있음을 나타내기 위해서)

인큐

원리는 간단하다. 항상 rear의 순서에 값을 넣는것.arr[rear] = var.

1. 일단 큐가 꽉 차있는지 확인한다. (방법은 밑에서)
2. rear = rear + 1 (밑에서 다시 확인)
3. arr[rear] 자리에 값을 삽입

디큐

제거할때는 반대로 항상 front의 순서에서 값을 제거하는것.

1. 일단 큐가 비어있는지 확인한다. (방법은 밑에서)
2. front = front +1; (밑에서 다시 확인)
3. arr[front]에 있는 값을 반환.

큐가 꽉 차있는지, 비어있는지 확인 (모듈러)

보통은 rear - front를 하면 어레이 안에 몇개의 값이 있는지 확인할 수있겠지만, 만약에 한바퀴 이상 돌아가서 rear < front 인 상황에선 어떻게 할까?

[5, ,2,3,4] 꽉 차있는 상황에서 rear가 0이고 front가 2이라고 가정.
이제 다음 차례니까 rear++가 돼서 rear는 1이 되고, 여기에 어레이의 크기인 5를 더해서 6-2 = 4 니까 비어있는 자리가 하나 있는걸 알 수 있다. 즉 rear % arr.length를 해서 거기서 front만큼 빼주면 되는것.
정리하자면 if((rear+1) % arr.length - front==0) 의 조건이 참이면 큐가 꽉 차있는지 확인할 수 있다.

그래서 사실 위에서 인큐과 디큐 과정에서 rear,front를 증가시킬 때 모듈러 계산을 넣어줘야 한다.
rear = (rear + 1) % arr.length
front = (front + 1) % arr.length

비어있는지 확인은 어떻게 하나?
비어있다는건 front값(마지막으로 디큐한 후의 인덱스)이 rear(마지막으로 인큐한 후의 인덱스)가 같다는 것과 같다.
비어있는지 확인은 디큐하기 전에 하는것이니까 [ , , ,1, ]를 디큐한다고 가정해보자.
마지막 인큐한 후의 rear는 3일것이고,
마지막 디큐한 후의 front는 2일것이다.
rear != front이니 디큐 과정을 진행할 수 있다.
(front + 1 ) % 5를 하면 3이 된다. 그리고 1을 반환하고 제거.

이제 다시 또 디큐를 시도해보면 front == rear 불가능하고 실제로 어레이도 비어있따.